package 简单算法;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-16
 * @Description: 写出一个高效的算法来搜索 m × n矩阵中的值。
 * 这个矩阵具有以下特性：每行中的整数从左到右是排序的。
 * 每行的第一个数大于上一行的最后一个整数。样例  1:
 * 输入: [[5]],2
 * 输出: false
 * 样例解释:
 * 没有包含，返回false。
 **/
public class 搜索二维矩阵 {

    public static void main(String[] args) {
        搜索二维矩阵 s = new 搜索二维矩阵();
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50}};
        System.out.println(s.searchMatrix(matrix, 50));
    }

    boolean result = false;

    public boolean searchMatrix(int[][] matrix, int target) {

        if (matrix == null || matrix.length == 0) {
            return false;
        }

        int index = 0;
        boolean flag = true;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][matrix[i].length - 1] >= target) {
                index = i;
                flag = true;
                break;
            } else {
                flag = false;
            }
//            for (int j = 0; j < matrix[i].length; j++) {
//                if(matrix[i][j]==target){
//                    return true;
//                }
//            }
        }

        if(!flag){
            return false;
        }

//        int start = 0;
//        dfs(matrix[index], start, target);

        int start = 0, end = matrix[index].length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (matrix[index][mid] == target) {
                end = mid;
            } else if (matrix[index][mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        if (matrix[index][start] == target) {
            result = true;
        }
        return result;
    }


    private void dfs(int[] matrix, int start, int target) {
        if (start == matrix.length) {
            result = false;
            return;
        } else {
            if (matrix[start] == target) {
                result = true;
                return;
            }
            dfs(matrix, ++start, target);
        }
    }


}
